Connectivity related concepts are of fundamental interest in graph theory.The area has received extensive attention over four decades, but many problemsremain unsolved, especially for directed graphs. A directed graph is2-edge-connected (resp., 2-vertex-connected) if the removal of any edge (resp.,vertex) leaves the graph strongly connected. In this paper we present improvedalgorithms for computing the maximal 2-edge- and 2-vertex-connected subgraphsof a given directed graph. These problems were first studied more than 35 yearsago, with $\widetilde{O}(mn)$ time algorithms for graphs with m edges and nvertices being known since the late 1980s. In contrast, the same problems forundirected graphs are known to be solvable in linear time. Henzinger et al.[ICALP 2015] recently introduced $O(n^2)$ time algorithms for the directedcase, thus improving the running times for dense graphs. Our new algorithms runin time $O(m^{3/2})$, which further improves the running times for sparsegraphs. The notion of 2-connectivity naturally generalizes to k-connectivity for$k>2$. For constant values of k, we extend one of our algorithms to compute themaximal k-edge-connected in time $O(m^{3/2} \log{n})$, improving again forsparse graphs the best known algorithm by Henzinger et al. [ICALP 2015] thatruns in $O(n^2 \log n)$ time.
展开▼
